import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {

        //分为前后半段哪边有序
        int leftIdx=0;
        int rightIdx=nums.length-1;

        while(leftIdx<=rightIdx){

            int midIdx=leftIdx+(rightIdx-leftIdx)/2;
            if(nums[midIdx]==target){
                return midIdx;
            }
            //nums[midIdx]>=nums[leftIdx]前半段有序
            if(nums[midIdx]>=nums[leftIdx]){
                if(nums[leftIdx]<=target&&target<nums[midIdx]){
                    //判断是否在前半段
                    rightIdx=midIdx-1;
                }else{
                    //不在前半段就在后半段
                    leftIdx=midIdx+1;
                }
            }else{
                //否则后半段有序
                if(nums[midIdx]<target&&target<=nums[rightIdx]){
                    //判断是否在后半段
                    leftIdx=midIdx+1;
                }else{
                    rightIdx=midIdx-1;
                }
            }
        }
        return -1;
    }
}